package puzzle.projecteuler.p300;

import java.math.BigInteger;

import astudy.util.AdvMath.Factors;

public class Problem251A {

	/**
	 * all (a,b,c) <=>
	 * a = 3*k+2
	 * b^2*c = (2*k+1)^3 + (3*k+2)^2 = (k+1)^2*(8*k+5)
	 * k >= 0
	 * 
	 * 注意:
	 * b+c = b/2 + b/2 + c >= 3*(b^2*c/4)^(1/3) > 3*2^(1/3)*(k+1)/ > 15*(k+1)/4
	 * 所以, a+b+c <= m => k < (4*m - 33)/27
	 * 
	 * 问题最大的困难是分解k+1或者8*k+5。
	 * 为了提高速度，需要能够快速的分解1～10^8所有数 
	 * 稍微估算一下需要的空间，1GB内存 = 10^9B
	 * 这样平均每个数分解的结果只能占用10B。
	 * 
	 * 目前程序按照下面方法尝试：开一个长度是10^8的数组A，A[i]只保存i的最小素因子。
	 * 这样做的好处：
	 * 1. 使用筛法就可迅速初始化该数组；
	 * 2. 很容易通过该数组计算出i的分解。
	 * 
	 * 
	 * answer	: 18946051
 	 * time cost: 1421078 ms
	 * @param args
	 */
	public static void main(String[] args) {

		long start = System.currentTimeMillis();
		
		int m = 110000000;
		BigInteger M = BigInteger.valueOf(m);
		int[] A = init((int)(32.0/27.0*m)+1);
		long count = 0;
		
		for (int k = 0; k <= (4*m - 33)/27; k ++) {
			
			if (k%1000000 == 0) {
				System.out.println((System.currentTimeMillis()-start) + " ms : " + k);
			}
			int a = 3*k+2;
			int x = k+1;
			int y = 8*k+5;
			Factors fx = findFactors(x, A);
			Factors fy = findFactors(y, A);
			Factors factors = fx.merge(fx).merge(fy);
			//get b
			int[] ns = new int[factors.size()];
			int index = 0;
			for (Long p: factors.keySet()) {
				ns[index++] = factors.get(p)/2;
			}
			int[] as = new int[factors.size()];
			for (int i = 0; i < as.length; i ++) as[i] = 0;
			
			BigInteger X = BigInteger.valueOf(x);
			BigInteger Y = BigInteger.valueOf(y);
			BigInteger T = X.multiply(X).multiply(Y);
			while (as != null) {
				BigInteger b = BigInteger.ONE;
				index = 0;
				for (Long p: factors.keySet()) {
					b = b.multiply(BigInteger.valueOf(p).pow(as[index++]));
				}
				BigInteger c = T.divide(b).divide(b);
				
				if (b.compareTo(M) <= 0 && c.compareTo(M) <=0 
						&& a + b.intValue() + c.intValue() <= m) {
					count ++;
//					System.out.println(a + ", " + b + ", " + c);
				}
				as = findNext(as, ns);
			}
		}
		System.out.println(count);
		System.out.println((System.currentTimeMillis()-start) + " ms");
	}
	
	/**
	 * 开一个长度是m的数组A，A[i]只保存i的最小素因子。
	 * @param m
	 * @return
	 */
	private static int[] init(int m) {
		
		if (m < 0) return null;
		
		int[] A = new int[m];
		if (m > 0) A[0] = -1;
		if (m > 1) A[1] = -1;
		
		int p = -1;
		for (int i = 2; i < m; i ++) {
			for (p = i; p < m; p ++) {
				if (A[p] == 0) {
					break;
				}
			}
			if (p*p >= m) break;
//			if (i%1000000 == 0) {
//				System.out.println(p);
//			}
			for (int j = p; j < m; j += p) {
				if (A[j] == 0) A[j] = p;
			}
		}
		
		for (int i = 2; i < m; i ++) {
			if (A[i] == 0) A[i] = i;
		}
		
		return A;
	}
	
	private static Factors findFactors(int n, int[] A) {
		
		Factors fs = new Factors();
		if (n == 1) {
			return fs;
		} else {
			long p = Long.valueOf(A[n]);
			int pow = 0;
			while (n % p == 0) {
				n /= p;
				pow ++;
			}
			fs.put(p, pow);
			Factors fs2 = findFactors(n, A);
			return fs2.merge(fs);
		}
	}

	/**
	 * copy from AdvMath.Factors.findNext(...)
	 * @param as
	 * @param ns
	 * @return
	 */
	private static int[] findNext(int[] as, int[] ns) {
		
		int j = ns.length-1;
		while (j > -1 && as[j] == ns[j]) j --;
		if (j == -1) {
			return null;
		} else {
			as[j] += 1;
			for (int i = j+1; i < ns.length; i ++) as[i] = 0;
			return as;
		}
	}
}
